package com.javabasic.algorithm.sword_of_offer;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/17 10:57 下午
 */
public class 剑指_Offer_57_和为s的两个数字 {

    /**
     * MAP+遍历
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        int len = nums.length, tag;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            if (nums[i] >= target) {
                break;
            }
            tag = map.getOrDefault(nums[i],0);
            tag++;
            map.put(nums[i], tag);
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] >= target) {
                break;
            }
            if (target == (nums[i] << 1)) {
                if (map.getOrDefault(nums[i],0) > 1) {
                    result[0] = nums[i];
                    result[1] = nums[i];
                    return result;
                }
            } else {
                if (map.getOrDefault(target - nums[i],0) > 0) {
                    result[0] = nums[i];
                    result[1] = target-nums[i];
                    return result;
                }
            }
        }
        return result;
    }


    /**
     * 双指针
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum2(int[] nums, int target) {
        int[] result = new int[2];
        int len = nums.length, left = 0, right = len-1;
        while (left < right) {
            if (nums[left] + nums[right] > target) {
                right--;
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                result[0] = nums[left];
                result[1] = nums[right];
                return result;
            }
        }

        return result;
    }
}
